CSE 373: Data Structures and Algorithms

Winter 2000

Assignment 3 Chapter 4 Solutions

1. Exercise 4.9 (4.9 in C++ book)

2. Exercise 4.23 (4.27 in C++ book) but only do it for keys 3 and 9 (if you can do those two you’ll understand the general idea of splaying)

3. Exercise 4.24 (4.28 in C++ book) but delete the key 6 from the original figure, not the resulting tree from the preceding problem.

4. Starting with the 2-3 tree on page 134 show the results of adding the key 64. Then show the results of deleting the key value 17. For those without the C book here is a crude representation of the starting 2-3 tree.

_________________
(_______22:-______)
/ \
/ \
____ _/ \_______
( 16:- ) ( 41:58 )
/ \ / | \
____/____ _\_____ __________/ ___|___ \__________
[ 8,11,12 ] [ 16,17 ] [ 22,23,31 ] [ 41,52 ] [ 58,59,61 ]

Here's the solution by Jindong Fang. Your TA is too lazy to draw the graph.

5. Assume you’ve been asked to design a set of routines to traverse a binary search tree and the data structure you are given has three pointers, a parent pointer, left child pointer, and right child pointer.
   
   typedef struct _TREE_NODE {
   struct _TREE_NODE *Parent;
   struct _TREE_NODE *LeftChild;
   struct _TREE_NODE *RightChild;
   } TREE_NODE *PTREE_NODE;
   
   Assume also that for the root node’s parent point is null. With this structure describe four algorithms that given any node in the tree will return
   
   (1) the sub-tree predecessor,
   (2) the sub-tree successor,
   (3) the complete-tree predecessor, and
   (4) the complete-tree successor.
   
   By sub-tree I mean that the node you are given should be treated as the root of its little tree, even though it may not be. Therefore the sub-tree procedure only considers direct descendants of the node, whereas the complete-tree procedure needs to potentially consider all the nodes in the entire tree. Each routine can also return NULL if the node does not have a successor predecessor. For example, in the following tree the sub-tree predecessor of C if null while its complete tree predecessor is A.
   
   A
   / \
   B C
   / \ \
   D E F
   
   

5pts for (1) & (2), 10 pts for (3) & (4).

Subtree predecessor:

return the rightmost node of the left subtree of the given node.

node* subtree_predecessor(node* p)

{

    if (!p->left)

        return NULL;

    node* pItr=p->left;

    while (pItr->right!=NULL)

        pItr=pItr->right;

    return pItr;

}

Subtree successor:

return the leftmost node of the right subtree of the given node.

node* subtree_successor(node* p)

{

    if (!p->right)

        return NULL;

    node* pItr=p->right;

    while (pItr->left!=NULL)

        pItr=pItr->left;

    return pItr;

}

Complete tree predecessor

If there is a subtree predecessor,  return the subtree predecessor.

else trace up the tree by following the parent pointers until you see a node is the right child of its parent, i.e. until you see a node whose value is smaller than the given node's. If the root is reached before you find such a node, that means the given node is the leftmost node of the whole tree, it has no predecessor.

node* completetree_predecessor(node* p)

{

    node* pItr=subtree_predecessor(*p);

    if (pItr)

        return pItr;

    pItr=p->parent;

    while (pItr!=NULL && pItr->data>=p->data)

        pItr=pItr->parent;

    return pItr;

}

Complete Tree Successor:

If there is a subtree successor, return the subtree successor.

else trace up the tree by following the parent pointers until you see a node is the left child of its parent, i.e. until you see a node whose value is greater than the given node's. If the root is reached before you find such a node, that means the given node is the rightmost node of the whole tree, it has no successor.

node* completetree_successor(node* p)

{

    node* pItr=subtree_successor(*p);

    if (pItr)

        return pItr;

    pItr=p->parent;

    while (pItr!=NULL && pItr->data<=p->data)

        pItr=pItr->parent;

    return pItr;

}